package codingforgreat.class10;

public class Class04_BSTtoDoubleLinkedList {
    // 提交时不要提交这个类
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    public static class Info{
        public Node start;
        public Node end;

        public Info(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }
    public static Node treeToDoublyList(Node head) {
        Info info = process(head);
        info.start.left = info.end;
        info.end.right = info.start;
        return info.start;
    }

    public static Info process(Node root){
        if(root == null){
            return  new  Info(null,null);
        }
        Info left = process(root.left);
        Info right = process(root.right);
        if(left.end != null){
            left.end.right = root;
        }
        if(right.start != null){
            right.start.left = root;
        }
        root.left = left.end;
        root.right = right.start;
        return new Info(left.start != null ? left.start : root, right.end != null ? right.end : root);
    }
}
